home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12923 < prev    next >
Encoding:
Text File  |  1996-08-05  |  3.1 KB  |  99 lines
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Recursion
  5. Date: 3 Apr 1996 07:15:35 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4ju4mnINN1qb@keats.ugrad.cs.ubc.ca>
  8. References: <31624BC2.70D2@sooner.net>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <31624BC2.70D2@sooner.net>, Eddie Bush  <edwbush@sooner.net> wrote:
  12. >I am trying to construct a C function that will recursively convert
  13. >a string such as "1234" into it's integer equivelant (1234).
  14. >
  15. >Here is what I know:
  16. >1)if you subtract the character "0" from any of the other digits "1".."9"
  17. >  you will get the integer value of that characer.
  18. >    Example:  "1" - "0" is equal to 1
  19. >          "2" - "0" is equal to 2
  20. >          .
  21. >          .
  22. >          .
  23. >          "9" - "0" is equal to 9
  24. >2)the function should be called with a character pointer:
  25. >    Such as:   convert("1234");
  26. >  making the prototype look something like:
  27. >    int convert(char *p);
  28. >
  29. >Does anyone have an idea?  This is sorta stumping me.  I am aware of 
  30. >atoi, but I am wanting to write a recursive function that does that -- 
  31. >for the fun of it.  It's sort of a little puzzle to help me learn 
  32. >recursion.  Any ideas?
  33.  
  34. Sounds more like a puzzle to earn a grade in a introductory programming course.
  35. Nobody would waste time by rewriting atoi() using recursion, unless it's
  36. homework. Plus if you really wanted a challenging puzzle, would you not solve
  37. it yourself?
  38.  
  39. In any case, you can use a "multiply and surrender approach" (which is a name
  40. given to any mis-application of the divide and conquer approach).
  41.  
  42. The integer value of a string can be recursively defined as the value of the
  43. least significant digit, plus the value of the rest of the string times 10.
  44.  
  45. For example, atoi("12345") == atoi("1234") * 10 + atoi("5");
  46.  
  47. This is one way to define it recursively.
  48.  
  49. I recommend that you reverse the digits contained in the string first. This may
  50. involve making a static copy of the string, or making an agreement with the
  51. caller that the string will be modified. Or you can make a local copy of the
  52. string which you reverse. Either way, you will probably want a ``wrapper''
  53. function which reverses the digits and then calls the actual function, let's
  54. call it val().
  55.  
  56. With the digits reversed,  the value of "1234" is just  val("4321") which is
  57. just 4 + 10 * val("321"). It is much easier to extract the digits from the
  58. beginning of a string just by advancing a pointer rather than searching to the
  59. end of a string in each recursive call.
  60.  
  61. #include <stdio.h>
  62. #include <stdlib.h>
  63. #include <string.h>
  64.  
  65. #define VAL(c) ((c) - '0')
  66.  
  67. long val(const char *str)
  68.  
  69. /* no overflow or illegal char checking    */
  70. /* takes a _reversed_ digit string    */
  71.  
  72. {
  73.     if(!*str)    /* at the end of string, return zero    */
  74.         return 0;
  75.     else
  76.         return    /* you ``puzzle'' this part out!    */;
  77. }
  78.  
  79.  
  80. long ratoi(const char *str)
  81.  
  82. {
  83.     char *tmp = malloc(strlen(str) + 1);
  84.     int value;
  85.  
  86.     /* should be checking for malloc() failure            */
  87.  
  88.     strcpy(tmp, str);
  89.  
  90.     /* now reverse it - look up in K&R2 how to do this or figure out */
  91.  
  92.     value = val(tmp);
  93.     free(tmp);
  94.  
  95.     return val;
  96. }
  97. -- 
  98.  
  99.